package com.demo.java.OD551_600.OD556;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【符合要求的元组的个数 or K数之和(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146534540
 */
public class OdMain {
    public static int result = 0; // 用于存储符合条件的组合数量
    public static int k; // 需要选取的元素个数

    public static void main(String[] args) {
        // 输入数据
        Scanner in = new Scanner(System.in);
        int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        k = Integer.parseInt(in.nextLine()); // 需要选取的元素个数
        int target = Integer.parseInt(in.nextLine()); // 目标和
        Arrays.sort(nums); // 对数组进行排序

        // 调用回溯函数计算符合条件的组合数量
        dfs(nums, target, 0, 0, 0);

        // 输出结果
        System.out.println(result);
    }

    // 回溯函数
    public static void dfs(int[] nums, int target, int pos, int sum_val, int count) {
        int i = pos;

        while (i < nums.length) {
            // 跳过重复的元素
            if (i > pos && nums[i - 1] == nums[i]) {
                i += 1;
                continue;
            }

            // 如果选择了k个元素，检查其和是否等于目标值
            if (count + 1 == k) {
                if (sum_val + nums[i] == target) {
                    result += 1; // 找到一个符合条件的组合
                }
                i += 1;
                continue;
            } else {
                // 否则继续选择下一个元素
                dfs(nums, target, i + 1, sum_val + nums[i], count + 1);
            }
            i += 1;
        }
    }
}